package lcr;

import java.util.ArrayList;
import java.util.List;

public class Test0087 {
    public static void main(String[] args) {
        new Solution0087_1().restoreIpAddresses("010010");
    }
}

class Solution0087_1 {
    List<String> ans=new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        traceback(s,new StringBuilder(),0,1);
        return ans;
    }

    public void traceback(String s,StringBuilder sb,int start,int count){
        int temp = sb.length();
        if (count==4){
            String str = isRegular(s, start, s.length(), count);
            if (str!=null){
                sb.append(str);
                ans.add(sb.toString());
                sb.setLength(temp);
            }
            return;
        }

        for (int i = start; i<start+3&&i < s.length(); i++) {
            String str = isRegular(s, start, i + 1, count);
            if (str!=null){
                sb.append(str).append('.');
                traceback(s,sb,i+1,count+1);
                sb.setLength(temp);
            }
        }
    }

    public String isRegular(String s,int start,int end,int count){
        int length = s.length();
        if ((end-start==1||s.charAt(start)!='0')
                &&end-start<=3&&end-start>0
                &&length-end<=3*(4-count)&&length-end>=4-count){
            String str = s.substring(start, end);
            return Integer.parseInt(str)<=255?str:null;
        }

        return null;
    }
}


